#include"Sort.h"
#include"stack.h"
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
//////
//////// 创建N个随机数，写到文件中
//////void CreateNDate()
//////{
//////    // 造数据
//////    int n = 10000000;
//////    srand(time(0));
//////    const char* file = "data.txt";
//////    FILE* fin = fopen(file, "w");
//////    if (fin == NULL)
//////    {
//////        perror("fopen error");
//////        return;
//////    }
//////
//////    for (int i = 0; i < n; ++i)
//////    {
//////        int x = rand() + i;
//////        fprintf(fin, "%d\n", x);
//////    }
//////
//////    fclose(fin);
//////}
//////
//////int compare(const void* a, const void* b)
//////{
//////    return (*(int*)a - *(int*)b);
//////}
//////
//////// 返回实际读到的数据个数，没有数据了，返回0
//////int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
//////{
//////    int x = 0;
//////    int* a = (int*)malloc(sizeof(int) * n);
//////    if (a == NULL)
//////    {
//////        perror("malloc error");
//////        return 0;
//////    }
//////
//////    // 想读取n个数据，如果遇到文件结束，应该读到j个
//////    int j = 0;
//////    for (int i = 0; i < n; i++)
//////    {
//////        if (fscanf(fout, "%d", &x) == EOF)
//////            break;
//////
//////        a[j++] = x;
//////    }
//////
//////    if (j == 0)
//////    {
//////        free(a);
//////        return 0;
//////    }
//////
//////    // 排序
//////    qsort(a, j, sizeof(int), compare);
//////
//////    FILE* fin = fopen(file1, "w");
//////    if (fin == NULL)
//////    {
//////        free(a);
//////        perror("fopen error");
//////        return 0;
//////    }
//////
//////    // 写回file1文件
//////    for (int i = 0; i < j; i++)
//////    {
//////        fprintf(fin, "%d\n", a[i]);
//////    }
//////
//////    free(a);
//////    fclose(fin);
//////
//////    return j;
//////}
//////
//////void MergeFile(const char* file1, const char* file2, const char* mfile)
//////{
//////    FILE* fout1 = fopen(file1, "r");
//////    if (fout1 == NULL)
//////    {
//////        perror("fopen error");
//////        return;
//////    }
//////
//////    FILE* fout2 = fopen(file2, "r");
//////    if (fout2 == NULL)
//////    {
//////        perror("fopen error");
//////        return;
//////    }
//////
//////    FILE* mfin = fopen(mfile, "w");
//////    if (mfin == NULL)
//////    {
//////        perror("fopen error");
//////        return;
//////    }
//////
//////    // 归并逻辑
//////    int x1 = 0;
//////    int x2 = 0;
//////    int ret1 = fscanf(fout1, "%d", &x1);
//////    int ret2 = fscanf(fout2, "%d", &x2);
//////    while (ret1 != EOF && ret2 != EOF)
//////    {
//////        if (x1 < x2)
//////        {
//////            fprintf(mfin, "%d\n", x1);
//////            ret1 = fscanf(fout1, "%d", &x1);
//////        }
//////        else
//////        {
//////            fprintf(mfin, "%d\n", x2);
//////            ret2 = fscanf(fout2, "%d", &x2);
//////        }
//////    }
//////
//////    while (ret1 != EOF)
//////    {
//////        fprintf(mfin, "%d\n", x1);
//////        ret1 = fscanf(fout1, "%d", &x1);
//////    }
//////
//////    while (ret2 != EOF)
//////    {
//////        fprintf(mfin, "%d\n", x2);
//////        ret2 = fscanf(fout2, "%d", &x2);
//////    }
//////
//////    fclose(fout1);
//////    fclose(fout2);
//////    fclose(mfin);
//////}
//////
//////
//////
//////    
//////        
//////        
//////
//////        
//////        
////
////        
////

////
////
////
////
//插入排序
// 时间复杂度：O(N^2)  什么情况最坏：逆序  最好：顺序有序，O(N)
void InsertSort(int* a, int n)	//传入数组的首地址和数组的大小
{
	// [0, n-2]是最后一组待排序列
	// [0,end]是有序，将end+1位置的值插入[0,end]，并使[0，end+1]保持有序

	for (int i = 0; i < n - 1; i++)	//i<n-1是为了防止下面tmp的end+1越界访问
	{
		int end = i;	//待排数列的最后一个被比数	
						//因为下面要对end--来达到对待排数列单趟排序的效果，所以不能直接用i，否则会影响到整体排序
		int tmp = a[end + 1];	//比数	//tmp范围是[1,n-1]

		while (end >= 0)	//单趟排序
		{
			if (tmp < a[end])			//只要比数小于前边的被比数
			{
				a[end + 1] = a[end];	//就将当前的被比数向后移
				--end;					//然后再去比较前一个被比数	
			}
			else
			{
				break;	//为了防止前边的数（被比数）都比待排数（比数）大
			}			//循环一直end--，直到不满足条件跳出循环，都没有进入else插入待排数的情况出现
		}				//因此要在循环的外面进行插值，而不是else中。
		a[end + 1] = tmp;	//当进行到这条语句就只有两种可能：待排数为最小和找到了比待排数小的数
	}						//此时都可以将值放到a[end-1]中
}

//
//
////希尔排序
//// O(N ^ 1.3)
//void ShellSort(int* a, int n)
//{
//	int gap = n;//gap是距离，是每一组中待排数之间的距离，也是每组的第一个待排数的距离
//	while (gap > 1)
//	{
//		// gap > 1时是预排序
//		// gap == 1时是插入排序
//		gap = gap / 3 + 1;	// +1保证最后一个gap一定是1
//
//		//从这里开始，就是插入排序了，只不过是分成了gap组同时进行
//		//当gap等于1的时候，就是把所有数分成一组，也就是上边的插入排序
//		for (size_t i = 0; i < n - gap; ++i)	//i < n-gap 依然是防止tmp越界访问
//		{
//			int end = i;
//			int tmp = a[end + gap];	
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{	
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//	}
//}
//
//////堆排序
//////void HeapSort(int* a, int n);
////
////
////
////数据交换
//void Swap(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//
//////直接选择排序（优化版：一趟同时确定最大和最小）
////// O(N^2)
////void SelectSort(int* a, int n)	//传入数组的地址和大小
////{
////	int begin = 0, end = n - 1;	//	标记待排数列的首尾
////
////	while (begin < end)	//只要begin和end没有相交，就一直循环
////	{
////		int mini = begin, maxi = begin;	//因为begin和end在不断向中心靠拢，所以也要在while循环中更新mini和maxi的初始指向
////		for (int i = begin + 1; i <= end; ++i)//单趟排序
////		{
////			if (a[i] > a[maxi])
////			{
////				maxi = i;
////			}
////			//通过将a[i]的下标赋值给mini和maxi来更新mini和maxi的指向
////			//保证所指向的数一定是此趟当前遍历到的最大值和最小值
////			if (a[i] < a[mini])
////			{
////				mini = i;
////			}
////		}
////		//上边的for循环，利用mini,i,maxi三个指针就将一趟中的最大值和最小值找到了
////
////		//下面通过数据交换函数将mini,i,maxi三个指针找到的最大值和最小值与begin和end进行交换
////		Swap(&a[begin], &a[mini]);
////		if (begin == maxi)		//防止在maxi和begin恰好都指向最大值时，因为mini和begin的交换，导致maxi找不到自己指向的值
////			maxi = mini;
////
////		Swap(&a[end], &a[maxi]);
////
////		//然后将两指针向中间靠拢，进行第二趟排序，找数组的第二大和第二小
////		++begin;
////		--end;
////	}
////}
////
////
////冒泡排序
//// O(N^2) 最坏
//// O(N)   最好
//void BubbleSort(int* a, int n)
//{
//	for (int j = 0; j < n; j++)
//	{
//		// 单趟
//		int flag = 0;
//		for (int i = 1; i < n - j; i++)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				flag = 1;
//			}
//		}
//
//		if (flag == 0)
//		{
//			break;
//		}
//	}
//}
//
////
////
////
//////hoare完整版
////void QuickSort(int* a, int left, int right)
////{
////	//递归的结束条件——如果下面有小区间优化则这个递归结束条件可有可无
////	//if (left >= right)
////	//	return;
////
////	//小区间优化，不在递归分割排序，减少递归的次数
////	if((right - left + 1) < 10)
////	{
////		//当向下递到小区间的待排值不足10个时，使用插入排序
////		InsertSort(a + left, right - left + 1);//传入的是小区间的最左和小区间的最右
////	}
////	else 
////	{
////		// 三数取中
////		int midi = GetMidi(a, left, right); //通过三数取中获得了一个较中的值的下标
////		Swap(&a[left], &a[midi]);	//将最左边的数和较中值进行位置交换
////
////		//设最左边的值为key
////		int keyi = left;
////		int begin = left, end = right;
////		while (begin < end)	//当begin != end 时，两指针就相遇了
////		{
////			// 右边找小
////			while (begin < end && a[end] >= a[keyi])	//右指针 < key 时跳出循环
////			{
////				--end;
////			}
////
////			// 左边找大
////			while (begin < end && a[begin] <= a[keyi])	//左指针 > key 时跳出循环
////			{
////				++begin;
////			}
////
////			//两循环都跳出时，说明右边小值和左边大值都找到了
////			Swap(&a[begin], &a[end]);	//交换两值位置
////		}
////		//跳出循环就证明两个指针已经完成任务并相遇
////		
////		Swap(&a[keyi], &a[begin]); //将相遇点的值与最左边的key值进行交换
////		keyi = begin;	//让key到相遇点上分割子区间
////		// [left, keyi-1] keyi [keyi+1, right]
////		QuickSort(a, left, keyi - 1);
////		QuickSort(a, keyi + 1, right);
////		//向子区间递下去
////	}
////	
////}
////
////
////三数取中优化函数
//int GetMidi(int* a, int left, int right)	//传入数组的地址和指向头尾的两个指针
//{
//	int midi = (left + right) / 2;
//	// left midi right
//
//	//通过if判断结构，使头中尾三个数的数值进行比较，返回中间值的下标
//	if (a[left] < a[midi])
//	{
//		if (a[midi] < a[right])
//		{
//			return midi;
//		}
//		else if (a[left] < a[right])
//		{
//			return right;
//		}
//		else
//		{
//			return left;
//		}
//	}
//	else // a[left] > a[midi]
//	{
//		if (a[midi] > a[right])
//		{
//			return midi;
//		}
//		else if (a[left] < a[right])
//		{
//			return left;
//		}
//		else
//		{
//			return right;
//		}
//	}
//}
//
////
////
////
////void QuickSort(int* a, int left, int right)
////{
////	if (left >= right)
////		return;
////
////	int keyi = PartSort1(a, left, right);
////
////	// [left, keyi-1] keyi [keyi+1, right]
////	QuickSort(a, left, keyi - 1);
////	QuickSort(a, keyi + 1, right);
////}
////
////
////
////// 前后指针
////int PartSort2(int* a, int left, int right)
////{
////	// 三数取中
////	int midi = GetMidi(a, left, right);
////	Swap(&a[left], &a[midi]);
////	int keyi = left;
////
////	int prev = left;
////	int cur = prev + 1;
////	while (cur <= right)
////	{
////		if (a[cur] < a[keyi] && ++prev != cur)
////			Swap(&a[prev], &a[cur]);
////
////		cur++;
////	}
////
////	Swap(&a[prev], &a[keyi]);
////	return prev;
////}
////
////
//////前后指针完整版
////void QuickSort(int* a, int left, int right)
////{
////	//递归的结束条件——如果下面有小区间优化则这个递归结束条件可有可无
////	//if (left >= right)
////	//	return;
////
////	//小区间优化，不在递归分割排序，减少递归的次数
////	if ((right - left + 1) < 10)
////	{
////		//当向下递到小区间的待排值不足10个时，使用插入排序
////		InsertSort(a + left, right - left + 1);//传入的是小区间的最左和小区间的最右
////	}
////	else
////	{
////		// 三数取中
////		int midi = GetMidi(a, left, right); //通过三数取中获得了一个较中的值的下标
////		Swap(&a[left], &a[midi]);	//将最左边的数和较中值进行位置交换
////
////		//设最左边的值为key
////		int keyi = left;
////		// 三数取中
////		int midi = GetMidi(a, left, right);
////		Swap(&a[left], &a[midi]);
////		int keyi = left;
////
////		int prev = left;
////		int cur = prev + 1;
////		while (cur <= right)
////		{
////			if (a[cur] < a[keyi] && ++prev != cur)
////				Swap(&a[prev], &a[cur]);
////
////			cur++;
////		}//跳出循环就证明cur指针已经走到底了，这时的prev指针左边都是小于key值的，右边都是大于key值的
////
////		Swap(&a[prev], &a[keyi]);//将相遇点的值与最左边的key值进行交换
////		
////		keyi = prev;	//让key到prev点上分割子区间
////		// [left, keyi-1] keyi [keyi+1, right]
////		QuickSort(a, left, keyi - 1);
////		QuickSort(a, keyi + 1, right);
////		//向子区间递下去
////	}
////
////}
////
////
////
//
//
//#include"stack.h"
//
////非递归版
//void QuickSortNonR(int* a, int left, int right)
//{
//	ST st;
//	STInit(&st);
//	STPush(&st, right);
//	STPush(&st, left);
//	
//	
//	while (!STEmpty(&st))
//	{
//		int begin = STTop(&st);
//		STPop(&st);
//		int end = STTop(&st);
//		STPop(&st);
//
//		int keyi = PartSort2(a, begin, end);
//		// [begin, keyi-1] keyi [keyi+1, end]
//		PrintArray(a, 7);
//		if (keyi + 1 < end)
//		{
//			STPush(&st, end);
//			STPush(&st, keyi + 1);
//		}
//
//		if (begin < keyi - 1)
//		{
//			STPush(&st, keyi - 1);
//			STPush(&st, begin);
//		}
//	}
//
//	STDestory(&st);
//}
//
//// 前后指针
//int PartSort2(int* a, int left, int right)
//{
//	// 三数取中
//	int midi = GetMidi(a, left, right);
//	Swap(&a[left], &a[midi]);
//	int key = left;
//
//	int prev = left;
//	int cur = prev + 1;
//	while (cur <= right)
//	{
//		if (a[cur] < a[key] && ++prev != cur)
//			Swap(&a[prev], &a[cur]);
//
//		cur++;
//		
//	}
//
//	Swap(&a[prev], &a[key]);
//	return prev;
//}
////
////
////
////
////
////
////
////
////
////
////
// //时间复杂度：O(N*logN)
// //空间复杂度：O(N)
// //17:13
//void _MergeSort(int* a, int* tmp, int begin, int end)
//{
//	if (begin >= end)
//		return;
//
//	int mid = (begin + end) / 2;
//	 //如果[begin, mid][mid+1, end]有序就可以进行归并了
//	_MergeSort(a, tmp, begin, mid);
//	_MergeSort(a, tmp, mid + 1, end);
//
//	// 归并
//	int begin1 = begin, end1 = mid;
//	int begin2 = mid + 1, end2 = end;
//	int i = begin;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (a[begin1] <= a[begin2])
//		{
//			tmp[i++] = a[begin1++];
//		}
//		else
//		{
//			tmp[i++] = a[begin2++];
//		}
//	}
//
//	while (begin1 <= end1)
//	{
//		tmp[i++] = a[begin1++];
//	}
//
//	while (begin2 <= end2)
//	{
//		tmp[i++] = a[begin2++];
//	}
//
//	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
//
//}
//
//
//
//
//
//void MergeSort(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//
//	_MergeSort(a, tmp, 0, n - 1);
//
//	free(tmp);
//	tmp = NULL;
//}

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	// gap每组归并数据的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 第二组都越界不存在，这一组就不需要归并
			if (begin2 >= n)
				break;

			// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
			if (end2 >= n)
				end2 = n - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}

		printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

// 时间复杂度:O(N+range)
// 只适合整数/适合范围集中
// 空间范围度：O(range)
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	//printf("%d\n", range);

	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}

	free(count);
}


//冒泡排序
// O(N^2) 最坏
// O(N)   最好
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}


//hoare版
void QuickSort(int* a, int left, int right)
{
	//递归的结束条件——如果下面有小区间优化则这个递归结束条件可有可无
	//if (left >= right)
	//	return;

	//小区间优化，不在递归分割排序，减少递归的次数
	if ((right - left + 1) < 10)
	{
		//当向下递到小区间的待排值不足10个时，使用插入排序
		InsertSort(a + left, right - left + 1);//传入的是小区间的最左和小区间的最右
	}
	else
	{
		// 三数取中
		int midi = GetMidi(a, left, right); //通过三数取中获得了一个较中的值的下标
		Swap(&a[left], &a[midi]);	//将最左边的数和较中值进行位置交换

		//设最左边的值为key
		int keyi = left;
		int begin = left, end = right;
		while (begin < end)	//当begin != end 时，两指针就相遇了
		{
			// 右边找小
			while (begin < end && a[end] >= a[keyi])	//右指针 < key 时跳出循环
			{
				--end;
			}

			// 左边找大
			while (begin < end && a[begin] <= a[keyi])	//左指针 > key 时跳出循环
			{
				++begin;
			}

			//两循环都跳出时，说明右边小值和左边大值都找到了
			Swap(&a[begin], &a[end]);	//交换两值位置
		}
		//跳出循环就证明两个指针已经完成任务并相遇

		Swap(&a[keyi], &a[begin]); //将相遇点的值与最左边的key值进行交换
		keyi = begin;	//让key到相遇点上分割子区间
		// [left, keyi-1] keyi [keyi+1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
		//向子区间递下去
	}
}


//三数取中优化函数
int GetMidi(int* a, int left, int right)	//传入数组的地址和指向头尾的两个指针
{
	int midi = (left + right) / 2;
	// left midi right

	//通过if判断结构，使头中尾三个数的数值进行比较，返回中间值的下标
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else // a[left] > a[midi]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


//前后指针
//void QuickSort(int* a, int left, int right)
//{
//	//递归的结束条件——如果下面有小区间优化则这个递归结束条件可有可无
//	//if (left >= right)
//	//	return;
//
//	//小区间优化，不在递归分割排序，减少递归的次数
//	if ((right - left + 1) < 10)
//	{
//		//当向下递到小区间的待排值不足10个时，使用插入排序
//		InsertSort(a + left, right - left + 1);//传入的是小区间的最左和小区间的最右
//	}
//	else
//	{
//		// 三数取中
//		int midi = GetMidi(a, left, right); //通过三数取中获得了一个较中的值的下标
//		Swap(&a[left], &a[midi]);	//将最左边的数和较中值进行位置交换
//
//		//设最左边的值为key
//		int keyi = left;
//		// 三数取中
//		int midi = GetMidi(a, left, right);
//		Swap(&a[left], &a[midi]);
//		int keyi = left;
//
//		int prev = left;	//将数组最左边的位置给prev指针
//		int cur = prev + 1;	//将prev指针后边的位置给cur指针
//		while (cur <= right)	//当cur还在范围内就一直遍历
//		{
//			if (a[cur] < a[keyi] && ++prev != cur)	//cur指针如果遍历到小于key的值，并且不挨着prev指针，就交换两个指针的值。
//				Swap(&a[prev], &a[cur]);
//
//			cur++;
//		}//跳出循环就证明cur指针已经走到底了，这时的prev指针左边都是小于key值的，右边都是大于key值的
//
//		Swap(&a[prev], &a[keyi]);//将相遇点的值与最左边的key值进行交换
//
//		keyi = prev;	//让key到prev位置上分割子区间
//
//		// [left, keyi-1] keyi [keyi+1, right]
//		QuickSort(a, left, keyi - 1);
//		QuickSort(a, keyi + 1, right);
//		//向子区间递下去
//	}
//
//}


//非递归版
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);	//对栈进行初始化
	//因为栈中存放的是整形结构，所以通过插入两次（区间右值和区间左值），来实现将待排区间压入栈中
	STPush(&st, right);
	STPush(&st, left);

	//循环每走一次，相当于之前快排的一次递归。
	while (!STEmpty(&st))
	{
		//首先取栈顶的待排区间
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		//将取到的区间传入开排函数中进行单趟排序，并返回排好之后的key值，用来分割子区间
		int keyi = PartSort2(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		//如果子区间里还有值，就把子区间右值和子区间左值压入栈中，准备下次循环取出子区间进行排序
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestory(&st);	//对栈进行销毁
}



// 前后指针版
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;

	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		cur++;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//数据交换
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}